package DFS递归搜索与回溯.综合;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Date 2024/9/16 14:58
 *
 * @description: N 皇后
 * .https://leetcode.cn/problems/n-queens/
 * @Author LittleNight
 */
public class likou51 {


    /**
     * N 皇后 练习
     * @param _n
     * @return
     */
    boolean[] checkCol, checkDig1, checkDig2;
    List<List<String>> ret;
    char[][] path;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new char[n][n];
        checkCol = new boolean[n];
        checkDig1 = new boolean[2 * n]; // 主副对角线空间应该是 2 * n
        checkDig2 = new boolean[2 * n];
        // 初始化path
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }
        dfs(0); // 只需要传递一个行数, 没有返回值
        return ret;
    }

    private void dfs(int row) {
        if(row == n) {
            // 添加结果
            List<String> tmp = new ArrayList<>();
            // 这里是到 n
            for (int i = 0; i < n; i++) {
//                tmp.add(new String(path[row]));
                tmp.add(new String(path[i]));
            }
            ret.add((new ArrayList<>(tmp)));
            return;
        }
        // 主逻辑
        for (int col = 0; col < n; col++) {
            // 看看能不能填, 剪枝
            if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                // 说明可以填
                path[row][col] = 'Q'; // 填表
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true; // 标记有了
                dfs(row + 1); // 进入下一层看看
                // 回溯-恢复现场
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }


//    boolean[] checkCol, checkDig1, checkDig2; // 列, 主对角线, 副对角线
//    List<List<String>> ret; // 结果集
//    char[][] path;
//    int n;
//    public List<List<String>> solveNQueens(int _n) {
//        // 初始化工作
//        n = _n;
//        checkCol = new boolean[n];
//        checkDig1 = new boolean[n * 2];
//        checkDig2 = new boolean[n * 2];
//        ret = new ArrayList<>();
//        path = new char[n][n];
//
//        // 初始化 path 数组. 全部先都填上.
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                path[i][j] = '.';
//            }
//        }
//        // 进行 dfs: 需要指定一个行数. 返回结果
//        dfs(0);
//        return ret;
//    }
//    // 遍历每一行
//    public void dfs(int row) {
//        // 递归出口, 行数填完
//        if(row == n) {
//            // 提取一行, 转为 String
//            List<String> tmp = new ArrayList<>();
//            for (int i = 0; i < n; i++) {
//                tmp.add(new String(path[i]));
//            }
//            // 添加到 ret 中, 需要重新 new 一个list
//            ret.add(new ArrayList<>(tmp));
//            return;
//        }
//        // dfs 主逻辑, 遍历这一行中的每一个列, 看看可不可以填
//        for (int col = 0; col < n; col++) {
//            // 判断可不可以填, 也就是剪枝. 列, 主副对角线都没填过
//            if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[col + row]) {
//                // 可以填
//                path[row][col] = 'Q'; // 填上 Q 皇后
//                checkCol[col] = checkDig1[row - col + n] = checkDig2[col + row] = true; // 标记已经填过
//                dfs(row + 1); // 进入下一层看看. 因为一定有结果, 所以不需要有返回值
//                // 回溯-恢复现场
//                path[row][col] = '.';
//                checkCol[col] = checkDig1[row - col + n] = checkDig2[col + row] = false;
//            }
//        }
//
//    }


}
